/**
 * @description: treeToArr
 * @author: huen2015
 */

interface IArrayData {
	id: number
	name: string
	parentId: number
	children?: IArrayData[]
}

interface ITreeData extends IArrayData {
	children?: IArrayData[]
}

/**
 * @description: 深度优先遍历（遍历 + 递归）
 * @param: tree: ITreeData => IArrayData[]
 * @author: huen2015
 */
function depthFirstTreeToArr(tree: ITreeData): IArrayData[] {
	const result: IArrayData[] = []
	const { id, name, parentId, children = [] } = tree
	if (id) {
		result.push({ id, name, parentId })
		if (children.length) {
			children.forEach((item: ITreeData) => {
				result.push(...depthFirstTreeToArr(item))
			})
		}
	}
	return result
}

/**
 * @description: 广度优先遍历（队列）
 * @param:
 * @author: huen2015
 */
function breadthFirstTreeToArr(tree: ITreeData): IArrayData[] {
	const result: IArrayData[] = []
	const queue: IArrayData[] = []
	queue.push(tree)

	while (queue.length) {
		const treeItem = queue.shift()
		if (treeItem) {
			const { id, name, parentId, children = [] } = treeItem
			result.push({ id, name, parentId })
			if (children.length) {
				children.forEach((item: ITreeData) => {
					queue.push(item)
				})
			}
		}
	}

	return result
}

const treeToArrData: ITreeData = {
	id: 1,
	name: '湖北省',
	parentId: 0,
	children: [
		{
			id: 2,
			name: '武汉市',
			parentId: 1,
			children: [
				{ id: 4, name: '武昌区', parentId: 2 },
				{ id: 5, name: '江岸区', parentId: 2 },
			],
		},
		{
			id: 3,
			name: '黄冈市',
			parentId: 1,
			children: [{ id: 6, name: '黄州区', parentId: 3 }],
		},
	],
}

const depthFirstTreeToArrResult = depthFirstTreeToArr(treeToArrData)
console.log('depthFirstTreeToArrResult', depthFirstTreeToArrResult)
const breadthFirstTreeToArrResult = breadthFirstTreeToArr(treeToArrData)
console.log('breadthFirstTreeToArrResult', breadthFirstTreeToArrResult)

export { depthFirstTreeToArr, breadthFirstTreeToArr }
